package com.captjack.math;

import java.math.BigInteger;

import static com.captjack.math.MatrixQuickPower.quickMatrixPower;

/**
 * @author Jack Sparrow
 * @version 1.0.0
 * @date 2022/10/14 18:49
 * package com.captjack.docker.simple.application
 */
public class Fibonacci {

    public static void main(String[] args) {
        int fib = fib();
        System.out.println("大于1000位的首个斐波那契项: " + fib);
        quickPower(1000000000);
        StringBuilder bigNum = new StringBuilder("1");
        for (int i = 0; i < 1000; i++) {
            bigNum.append("0");
        }
        quickBigPower(new BigInteger(bigNum.toString()));
    }

    public static int fib() {
        BigInteger pre = new BigInteger("1");
        BigInteger last = new BigInteger("1");
        for (int i = 3; i < Integer.MAX_VALUE; i++) {
            BigInteger temp = last;
            last = last.add(pre);
            pre = temp;
            if (last.toString().length() >= 1000) {
                return i;
            }
            if (i == 100) {
                System.out.println("第" + i + "项斐波那契数是: " + last);
            }
        }
        return -1;
    }

    public static void quickPower(long num) {
        long mod = (long) (1e9 + 7);
        long[][] init = new long[2][2];
        init[0][0] = 1;
        init[0][1] = 1;
        init[1][0] = 1;
        init[1][1] = 0;
        long[][] data = quickMatrixPower(init, num - 1, mod);
        System.out.println("第" + num + "项斐波那契数根据" + mod + "取模结果为: " + data[0][0]);
    }

    public static void quickBigPower(BigInteger num) {
        long mod = (long) (1e9 + 7);
        long[][] init = new long[2][2];
        init[0][1] = 1;
        init[0][0] = 1;
        init[1][0] = 1;
        init[1][1] = 0;
        long[][] data = quickMatrixPower(init, num.subtract(BigInteger.ONE), mod);
        System.out.println("第x项斐波那契数根据" + mod + "取模结果为: " + data[0][0]);
    }

}
